Developer CD Series 1996 June: Reference Library/Dev.CD Jun 96 RL/Dev.CD Jun 96 RL.toast/Technical Documentation/develop/develop Issue 24/develop Issue 24 code/Scriptable Database 1.0a15/Base/ListTemplate.h

C/C++ Source or Header | 1996-02-19 | 19.7 KB | 661 lines | [TEXT/CWIE]

#pragma once

#ifndef __LISTTEMPLATE__
#define __LISTTEMPLATE__

#define DEBUGPREEMPTIVELOCK 1

//
// For 'nil'
//
#include <Types.h>

//
// This is how many elements our list grows by every time we run
// out of space.  We could potentially be a lot more intelligent
// about our growing behavior.
//
// n.b. Currently these lists never trim, which could be bad.
//
#define kAllocationChunk            32

//
// We usually don't have more than two iterators on a list, so
// we'll only allocate space for the iterator list two elements
// at a time.
//
#define kIterListAllocationChunk    2

typedef Boolean (*ListElementCompareProcPtr)(const char* item1, const char* item2);


class TAbstractListIterator;

//================================================================================
// CLASS TListStorage
//
// This class is for use by the list template, and isn't intended for direct use.
//================================================================================

class TListStorage
{
    //
    // Only TAbstractListIterators may add or remove themselves
    // to our iterator list
    //
    friend class TAbstractListIterator;

public:
    TListStorage(UInt32 itemSize) :
        fListData(nil),
        fItemSize(itemSize),
        fItemsInList(0),
        fSpaceReserved(0),
#if DEBUGPREEMPTIVELOCK
        fReadLocks(0),
        fWriteLocks(0),
#endif
        fIteratorList(nil),
        fNumberOfIterators(0),
        fIteratorListReservedSpace(0) {}

    TListStorage(UInt32 itemSize, UInt32 initialItemSpace) :
        fListData(nil),
        fItemSize(itemSize),
        fItemsInList(0),
        fSpaceReserved(0),
#if DEBUGPREEMPTIVELOCK
        fReadLocks(0),
        fWriteLocks(0),
#endif
        fIteratorList(nil),
        fNumberOfIterators(0),
        fIteratorListReservedSpace(0) { this->InsureAdequateSpace(initialItemSpace); }

    TListStorage(const TListStorage& copyFrom);

    ~TListStorage();

    //
    // Simple list access
    //
    Boolean                    Empty() const                                    { return (this->ItemsInList() == 0); }
    UInt32                    ItemsInList() const                                { return fItemsInList; }

    //
    // Primary list-manipulation and item access API:
    //
    TListStorage*            Clone() const;

    //
    // Add an item to the list in no particular order (puts new
    // item in using the fastest insertion available)
    //
    void                    Add(const char* elementAddress);
    Boolean                    Remove(const char*, ListElementCompareProcPtr compareProc);

    //
    // n.b.    Inserting N items at the beginning of the list is O(N^2)
    //        Inserting N items at the end of the list is O(N)
    //        Inserting N items at the end of the list and reversing their order is also O(N).
    //
    void                    InsertAtBeginning(const char* elementAddress);
    void                    InsertAtEnd(const char* elementAddress);

    //
    // n.b.    Removing N items from the beginning of the list is O(N^2)
    //        Removing N items from the end of the list is O(N)
    //
    void                    RemoveFromBeginning();
    void                    RemoveFromEnd();

    //
    // List accessors
    //
    void                    FirstItem(char* copyToBuffer) const;
    void                    LastItem(char* copyToBuffer) const;

    //
    // Misc list manipulation
    //
    void                    ReverseOrderOfList(char* tempBuffer);
    void                    MakeEmpty();

    //
    // Access locks for preemptive software (see comment below)
    //
    void                    LockForReading() const;
    void                    RelinquishReadLock() const;
    void                    LockForWriting();
    void                    RelinquishWriteLock();

    //
    // Not preemptive-safe if called directly; however, ONLY
    // these routines + the "simple list access" routines may
    // be called if you explicitly lock a list for writing.
    //
    // If you explicitly lock a list for reading, it is okay
    // to call 'const' routines from above, but don't call any
    // routines that try to write, or you'll deadlock.
    //
    void                    ItemAtIndex(SInt32 itemIndex, char* copyToBuffer) const;
    void                    ReplaceItemAtIndex(SInt32 itemIndex, const char* dataToReplaceWith);
    void                    RemoveItemAtIndex(SInt32 itemIndex);
    SInt32                    IndexOfItem(const char*, ListElementCompareProcPtr compareProc, SInt32 indexToStartAt = 0) const;

private:

    //
    // Memory handling
    //
    void                    InsureAdequateSpace(SInt32 numberOfItems);

    //
    // Peeking at items:
    //
    const char*                ItemAddress(SInt32 itemIndex)    const                { return this->fListData + (itemIndex * fItemSize); }
    char*                    ItemAddress(SInt32 itemIndex)                        { return this->fListData + (itemIndex * fItemSize); }

    //
    // Keeping iterators in sync:
    //
    void                    AddIterator(TAbstractListIterator*);
    void                    RemoveIterator(TAbstractListIterator*);
    void                    InsureSpaceForIteratorList(UInt16 numberOfItersNeeded);

    void                    NotifyItemAdded(SInt32 indexOfNewItem);
    void                    NotifyItemRemoved(SInt32 indexOfItemRemoved);
    void                    NotifyListDestroyed();

private:
    char*                    fListData;
    UInt32                    fItemSize;
    UInt32                    fItemsInList;
    UInt32                    fSpaceReserved;

#if DEBUGPREEMPTIVELOCK
    UInt32                    fReadLocks;
    UInt32                    fWriteLocks;
#endif

    TAbstractListIterator**    fIteratorList;
    UInt16                    fNumberOfIterators;
    UInt16                    fIteratorListReservedSpace;
};

template <class T> class AnIteratorOfAListOf;

//================================================================================
// TEMPLATE AListOf
//================================================================================

template <class T> class AListOf
{
    //
    // This is only here so that the iterator can gain access to the
    // list storage object durring its constructor and destructor,
    // and thereby register itself with the list storage.
    //
    friend class AnIteratorOfAListOf<T>;

public:
    AListOf() :
        fListStorage(sizeof(T)) {}

    AListOf(SInt32 initialItems) :
        fListStorage(sizeof(T), initialItems) {}

    AListOf(const AListOf<T>& copyFrom) :
        fListStorage(copyFrom.fListStorage) {}

    //
    // Simple list access
    //
    Boolean                    Empty() const                                { return fListStorage.Empty(); }
    SInt32                    ItemsInList() const                            { return fListStorage.ItemsInList(); }

    //
    // Primary list-manipulation and item access API:
    //
    AListOf<T>*                Clone() const                                { AListOf<T>* clonedList = new AListOf<T>(*this); return clonedList; }

    //
    // Add an item to the list in no particular order (puts new
    // item in using the fastest insertion available)
    //
    void                    Add(const T& valueToAdd)                    { fListStorage.Add((const char*)&valueToAdd); }
    Boolean                    Remove(const T& valueToRemove)                { return fListStorage.Remove((const char*)&valueToRemove, CompareTwoElements); }

    //
    // n.b.    Inserting N items at the beginning of the list is O(N^2)
    //        Inserting N items at the end of the list is O(N)
    //        Inserting N items at the end of the list and reversing their order is also O(N).
    //
    void                    InsertAtBeginning(const T& valueToAdd)        { fListStorage.InsertAtBeginning((const char*)&valueToAdd); }
    void                    InsertAtEnd(const T& valueToAdd)            { fListStorage.InsertAtEnd((const char*)&valueToAdd); }

    //
    // n.b.    Removing N items from the beginning of the list is O(N^2)
    //        Removing N items from the end of the list is O(N)
    //
    void                    RemoveFromBeginning()                        { fListStorage.RemoveFromBeginning(); }
    void                    RemoveFromEnd()                                { fListStorage.RemoveFromEnd(); }

    //
    // List accessors
    //
    T                        FirstItem() const                            { T result; fListStorage.FirstItem((char*)&result); return result; }
    T                        LastItem() const                            { T result; fListStorage.LastItem((char*)&result); return result; }

    //
    // Misc list manipulation
    //
    void                    ReverseOrderOfList()                        { T tempStorage; fListStorage.ReverseOrderOfList((char*)&tempStorage); }
    void                    MakeEmpty()                                    { fListStorage.MakeEmpty(); }

    //
    // Synonyms, for those who care
    //
    void                    Push(const T& valueToPush)                    { this->InsertAtEnd(valueToPush); }
    T                        TopOfStackValue() const                        { return this->LastItem(); }
    T                        Pop()                                        { T temp = this->TopOfStackValue(); this->RemoveFromEnd(); return temp; }

    //
    // Enqueueing and dequeueing N items is O(N*D), where D is the
    // average depth of the queue.  This is O(N^2) for most uses.
    // O(N) algorithms exist, but currently are not implemented, as
    // they require leaving insertion gaps that either invalidate the
    // format of our list, or needlessly complicate the access for
    // all lists, even those not to be used as a queue.  If you
    // really need a fast queue, write a queue class, don't use this
    // template.
    //
    void                    Enqueue(const T& valueToQ)                    { this->InsertAtEnd(valueToQ); }
    T                        TopOfQueueValue() const                        { return this->FirstItem(); }
    T                        Dequeue()                                    { T temp = this->TopOfQueueValue(); this->RemoveFromBeginning(); return temp; }

    //
    // Access locks for preemptive software.
    //
    // These locks should be kept for a minimum amount of time.
    // Note that the methods above all call Lock/Relinquish as
    // necessary.
    //
    //    -    LockForReading blocks until the active writer (if any)
    //         relinquishes the write lock
    //    -    LockForWriting blocks until the active writer and all
    //         active readers (if any) relinquish their respective locks
    //
    // Every call to "Lock" must be (soon) balanced by a call to
    // "Relinquish"; calling LockForReading multiple times is okay,
    // as long as the calls to RelinquishReadLock balance the calls
    // to LockForReading.
    //
    // IMPORTANT:  There can only be one writer, so you will
    // block yourself forever (deadlock) if you try to LockForWriting.
    // twice.  You will also block yourself forever if you call
    // LockForWriting followed by a call to LockForReading (or
    // visa-versa).
    //
    // Therefore, calling the Lock routines directly is dangerous
    //
    void                    LockForReading() const                        { fListStorage.LockForReading(); }
    void                    RelinquishReadLock() const                    { fListStorage.RelinquishReadLock(); }
    void                    LockForWriting()                            { fListStorage.LockForWriting(); }
    void                    RelinquishWriteLock()                        { fListStorage.RelinquishWriteLock(); }

    //
    // WARNING:                The following routines are not pre-emptive safe if called directly,
    //                        because the index values may change at any instant if another task
    //                        modifies the list.
    //
    // Pre-emptive-safe alternatives:
    //
    // ItemAtIndex:            use an iterator and iter.Current()
    // ReplaceItemAtIndex:    use an iterator and iter.SetCurrent()
    // RemoveItemAtIndex:    use an iterator and iter.RemoveCurrent()
    // IndexOfItem:            use an iterator and iter.AdvanceToItem()
    //
    // If for some reason you have a burning desire to NOT use an
    // iterator, you may call these routines if you Lock/Relinquish
    // this list appropriately, but you must do so carefully if you
    // want to avoid deadlock.
    //
    T                        ItemAtIndex(SInt32 itemIndex) const                            { T result; fListStorage.ItemAtIndex(itemIndex, (char*)&result); return result; }
    void                    ReplaceItemAtIndex(SInt32 itemIndex, const T& newValue)        { fListStorage.ReplaceItemAtIndex(itemIndex, (char*)&newValue); }
    void                    RemoveItemAtIndex(SInt32 itemIndex)                            { fListStorage.RemoveItemAtIndex(itemIndex); }
    SInt32                    IndexOfItem(const T& itemToFind, SInt32 startAt = 0) const    { return fListStorage.IndexOfItem((const char*)&itemToFind, CompareTwoElements, startAt); }

protected:
    static Boolean            CompareTwoElements(const char* item1, const char* item2);

    //
    // The ListStorage accessor is only used by AnIteratorOfAListOf
    // to get the list storage to register itself with the list
    // storage.
    //
    TListStorage&            ListStorage() { return fListStorage; }

private:
    TListStorage            fListStorage;
};


//-------------------------------------------------------------------
// AListOf<T>::CompareTwoElements
//-------------------------------------------------------------------
template <class T>
Boolean AListOf<T>::CompareTwoElements(const char* item1, const char* item2)
{
    return ((T*)item1) == ((T*)item2);
}


//================================================================================
// CLASS TAbstractListIterator
//
// Abstract base class for iterators, so that we may keep track of our
// iterators in our list-storage class.
//================================================================================

class TAbstractListIterator
{
public:
    virtual void            NotifyItemAdded(SInt32 indexOfNewItem) = 0;
    virtual void            NotifyItemRemoved(SInt32 indexOfItemRemoved) = 0;
    virtual void            NotifyListDestroyed() = 0;

protected:
    void                    RegisterWithList(TListStorage& list)        { list.AddIterator(this); }
    void                    UnregisterWithList(TListStorage& list)        { list.RemoveIterator(this); }
};

//================================================================================
// TEMPLATE AnIteratorOfAListOf
//================================================================================

template <class T> class AnIteratorOfAListOf : public TAbstractListIterator
{
public:
    AnIteratorOfAListOf(AListOf<T>* inList, Boolean iterateBackwards = false) :
        fList(inList),
        fCurrentItem(0),
        fRemovedCurrent(false),
        fWeRemovedCurrent(false),
        fIterateBackwards(iterateBackwards) { this->RegisterWithList(fList->ListStorage()); this->Reset(iterateBackwards); }

    ~AnIteratorOfAListOf() { this->UnregisterWithList(fList->ListStorage()); }

    void                    Reset(Boolean iterateBackwards = false);

    Boolean                    More() const;
    UInt32                    ItemsRemainingToIterate() const;
    void                    Next();
    Boolean                    AdvanceToItem(const T&);

    const T&                Current() const;
    void                    SetCurrent(const T& newValue);
    void                    RemoveCurrent();

    virtual void            NotifyItemAdded(SInt32 indexOfNewItem);
    virtual void            NotifyItemRemoved(SInt32 indexOfItemRemoved);
    virtual void            NotifyListDestroyed();

private:
    AListOf<T>*                fList;
    SInt32                    fCurrentItem;
    Boolean                    fRemovedCurrent;
    Boolean                    fWeRemovedCurrent;
    Boolean                    fIterateBackwards;
};

//-------------------------------------------------------------------
// AnIteratorOfAListOf<T>::Reset
//-------------------------------------------------------------------
template <class T>
void AnIteratorOfAListOf<T>::Reset(Boolean iterateBackwards)
{
    if(fList != nil)
    {
        fList->LockForReading();
        fIterateBackwards = iterateBackwards;

        if(fIterateBackwards)
            fCurrentItem = fList->ItemsInList() - 1;
        else
            fCurrentItem = 0;
        fList->RelinquishReadLock();
    }
}

//-------------------------------------------------------------------
// AnIteratorOfAListOf<T>::More
//-------------------------------------------------------------------
template <class T>
Boolean AnIteratorOfAListOf<T>::More() const
{
    Boolean moreItems = false;

    if(fList != nil)
    {
        fList->LockForReading();
        moreItems = (fCurrentItem < fList->ItemsInList()) && (fCurrentItem >= 0);
        fList->RelinquishReadLock();
    }

    return moreItems;
}

//-------------------------------------------------------------------
// AnIteratorOfAListOf<T>::ItemsRemainingToIterate
//-------------------------------------------------------------------
template <class T>
UInt32 AnIteratorOfAListOf<T>::ItemsRemainingToIterate() const
{
    UInt32 remainingItems = 0;

    if(fList != nil)
    {
        if(fIterateBackwards)
            remainingItems = fCurrentItem + 1;
        else
        {
            fList->LockForReading();
            SInt32 totalItems = fList->ItemsInList();
            fList->RelinquishReadLock();

            remainingItems = totalItems - fCurrentItem;
        }
    }

    return remainingItems;
}

//-------------------------------------------------------------------
// AnIteratorOfAListOf<T>::Next
//-------------------------------------------------------------------
template <class T>
void AnIteratorOfAListOf<T>::Next()
{
    if(fList != nil)
    {
        //
        // We must lock for reading so that someone does not
        // come along and change the list (modifying our
        // fCurrentItem) while we are updating our iteration
        // state.
        //
        fList->LockForReading();
        if((fRemovedCurrent == false) && (this->More()))
        {
            if(fIterateBackwards)
                --fCurrentItem;
            else
                ++fCurrentItem;
        }
        fRemovedCurrent = false;
        fList->RelinquishReadLock();
    }
}

//-------------------------------------------------------------------
// AnIteratorOfAListOf<T>::AdvanceToItem
//
// n.b. If Current() == itemToFind, then this routine will NOT
// advance anywhere, so cal Next() between calls to AdvanceToItem()
// if you need to find every item of a given value in a list.
//
// fCurrentItem starts at the first item in the list, so this
// routine wouldn't be able to find the first item in a list
// if it skipped the current item before searching.
//-------------------------------------------------------------------
template <class T>
Boolean AnIteratorOfAListOf<T>::AdvanceToItem(const T& itemToFind)
{
    Boolean foundItem = false;

    if(fList != nil)
    {
        if(fIterateBackwards == true)
        {
            DebugStr("\pAdvanceToItem doesn't work right when iterating backwards.  switching to forward iteration");
            this->Reset(false);
        }

        fList->LockForReading();
        SInt32 foundIndex = fList->IndexOfItem(itemToFind, fCurrentItem);
        if(foundIndex != -1)
        {
            fCurrentItem = foundIndex;
            foundItem = true;
        }
        fList->RelinquishReadLock();
    }

    return foundItem;
}

//-------------------------------------------------------------------
// AnIteratorOfAListOf<T>::Current
//-------------------------------------------------------------------
template <class T>
const T& AnIteratorOfAListOf<T>::Current() const
{
    T result;

    if(fList != nil)
    {
        //
        // We must lock for reading so that someone does not
        // change the list in between the time we access our
        // field fCurrentItem and the time that ItemAtIndex
        // returns.
        //
        fList->LockForReading();
        result = fList->ItemAtIndex(fCurrentItem);
        fList->RelinquishReadLock();
    }

    return result;
}

//-------------------------------------------------------------------
// AnIteratorOfAListOf<T>::SetCurrent
//-------------------------------------------------------------------
template <class T>
void AnIteratorOfAListOf<T>::SetCurrent(const T& newValue)
{
    if(fList != nil)
    {
        fList->LockForWriting();
        fList->ReplaceItemAtIndex(fCurrentItem, newValue);
        fList->RelinquishWriteLock();
    }
}

//-------------------------------------------------------------------
// AnIteratorOfAListOf<T>::RemoveCurrent
//-------------------------------------------------------------------
template <class T>
void AnIteratorOfAListOf<T>::RemoveCurrent()
{
    if(this->More())
    {
        //
        // When we call 'RemoveItemAtIndex,' we
        // will be called back and our fCurrentItem
        // will be automatically updated, and
        // fRemovedCurrent will be set to true.
        //
        // The same thing would happen if someone
        // else removes our current item.
        //
        fList->LockForWriting();
        fList->RemoveItemAtIndex(fCurrentItem);
        fList->RelinquishWriteLock();

        fWeRemovedCurrent = true;
    }
}

//-------------------------------------------------------------------
// AnIteratorOfAListOf<T>::NotifyItemAdded
//-------------------------------------------------------------------
template <class T>
void AnIteratorOfAListOf<T>::NotifyItemAdded(SInt32 indexOfNewItem)
{
    //
    // If an item is inserted before our current item,
    // then we want to advance such that 'fCurrentItem'
    // still points at the same item it did before the
    // insertion happened.
    //
    if(indexOfNewItem <= fCurrentItem)
        ++fCurrentItem;
}

//-------------------------------------------------------------------
// AnIteratorOfAListOf<T>::NotifyItemRemoved
//-------------------------------------------------------------------
template <class T>
void AnIteratorOfAListOf<T>::NotifyItemRemoved(SInt32 indexOfItemRemoved)
{
    //
    // If someone removes our current item, then
    // we need to adjust for that fact.
    //
    if(indexOfItemRemoved == fCurrentItem)
    {
        //
        // Immediately adjust 'fCurrentItem' so that
        // it points to the next item, and remember
        // that the current item was removed so that
        // Next() will not advance again.
        //
        if(fIterateBackwards)
            --fCurrentItem;
        fRemovedCurrent = true;
        fWeRemovedCurrent = false;
    }
    //
    // If someone removes an item that is not our current
    // item, then adjust 'fCurrentItem' such that it still
    // points at the same item it did before the removal.
    //
    else if(indexOfItemRemoved < fCurrentItem)
    {
        --fCurrentItem;
    }
}

//-------------------------------------------------------------------
// AnIteratorOfAListOf<T>::NotifyListDestroyed
//-------------------------------------------------------------------
template <class T>
void AnIteratorOfAListOf<T>::NotifyListDestroyed()
{
    fList = nil;
}

#endif